package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class BinaryTreeZigzagLevelOrderTraversal {
	
	//方法一：DFS
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    	List<List<Integer>> result = new ArrayList<>();
    	zigzagLevelOrder(root, 0, result);
        return result;
    }
    
    private void zigzagLevelOrder(TreeNode node, int level, List<List<Integer>> result) {
    	if(node == null) return;
    	
		if(level == result.size()) {
			List<Integer> temp = new LinkedList<>();
			temp.add(node.val);
			result.add(temp);
		}else {
			List<Integer> temp = result.get(level);
			//偶数行的从左到右，奇数行的从右到左
			temp.add((level & 1) == 0 ? temp.size() : 0, node.val);
		}
    	
    	zigzagLevelOrder(node.left, level + 1, result);
    	zigzagLevelOrder(node.right, level + 1, result);
    }
    
    //方法二：BFS
    public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
    	List<List<Integer>> result = new ArrayList<>();
    	if(root == null) return result;
    	
    	LinkedList<TreeNode> queue = new LinkedList<>();
    	queue.offer(root);
    	int level = 0;
    	while(!queue.isEmpty()) {
    		List<Integer> temp = new LinkedList<>();
    		for(int size = queue.size(); size > 0; size--) {
    			TreeNode node = queue.pop();
    			//偶数行的从左到右，奇数行的从右到左
    			temp.add((level & 1) == 0 ? temp.size() : 0, node.val);
    			if(node.left != null)
    				queue.offer(node.left);
    			if(node.right != null)
    				queue.offer(node.right);    			
    		}
    		result.add(temp);
    		level++;
    	}
        return result;
    }
    
}
